{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #砍竹子 I"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: cuttingBamboo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #砍竹子 I"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>现需要将一根长为正整数 <code>bamboo_len</code> 的竹子砍为若干段，每段长度均为正整数。请返回每段竹子长度的最大乘积是多少。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>bamboo_len<strong> </strong>=<strong> </strong>12\n",
    "<strong>输出: </strong>81\n",
    "</pre>\n",
    "<strong>提示：</strong>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= bamboo_len&nbsp;&lt;= 58</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>注意：本题与主站 343 题相同：<a href=\"https://leetcode-cn.com/problems/integer-break/\">https://leetcode-cn.com/problems/integer-break/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [jian-sheng-zi-lcof](https://leetcode.cn/problems/jian-sheng-zi-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [jian-sheng-zi-lcof](https://leetcode.cn/problems/jian-sheng-zi-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['12']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3:\n",
    "            return bamboo_len - 1\n",
    "        \n",
    "        a = bamboo_len // 3\n",
    "        b = bamboo_len % 3\n",
    "        if b == 1 and a >= 1:\n",
    "            a -= 1\n",
    "            b = 4\n",
    "\n",
    "        return (3 ** a) % 1000000007 if b == 0 else ((3 ** a) * b) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3: return bamboo_len - 1\n",
    "        a, b, p, x, rem = bamboo_len // 3 - 1, bamboo_len % 3, 1000000007, 3 , 1\n",
    "        while a > 0:\n",
    "            if a % 2: rem = (rem * x) % p\n",
    "            x = x ** 2 % p\n",
    "            a //= 2\n",
    "        if b == 0: return (rem * 3) % p # = 3^(a+1) % p\n",
    "        if b == 1: return (rem * 4) % p # = 3^a * 4 % p\n",
    "        return (rem * 6) % p # = 3^(a+1) * 2 % p\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3: return bamboo_len - 1\n",
    "        a, b, p, x, rem = bamboo_len // 3 - 1, bamboo_len % 3, 1000000007, 3 , 1\n",
    "        while a > 0:\n",
    "            if a % 2: rem = (rem * x) % p\n",
    "            x = x ** 2 % p\n",
    "            a //= 2\n",
    "        if b == 0: return (rem * 3) % p # = 3^(a+1) % p\n",
    "        if b == 1: return (rem * 4) % p # = 3^a * 4 % p\n",
    "        return (rem * 6) % p # = 3^(a+1) * 2 % p\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3: return bamboo_len - 1\n",
    "        ans = 1\n",
    "        MOD = 10 ** 9 + 7\n",
    "        while bamboo_len > 4:\n",
    "            ans = (ans * 3) % MOD\n",
    "            bamboo_len -= 3\n",
    "        return (bamboo_len * ans) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        if bamboo_len < 4: \n",
    "            return bamboo_len - 1\n",
    "        q, r, x, res = bamboo_len // 3 - 1, bamboo_len % 3, 3, 1\n",
    "        while q:\n",
    "            if q % 2: res = (res * x) % MOD\n",
    "            x = x * x % MOD\n",
    "            q //= 2\n",
    "        if r == 0: return (res * 3) % MOD\n",
    "        if r == 1: return (res * 4) % MOD\n",
    "        return (res * 6) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3:\n",
    "            return bamboo_len - 1\n",
    "        if bamboo_len % 3 == 0:\n",
    "            return 3 ** (bamboo_len // 3) % 1000000007\n",
    "        if bamboo_len % 3 == 1:\n",
    "            return 3 ** ((bamboo_len - 4) // 3) * 4 % 1000000007\n",
    "        return 3 ** ((bamboo_len - 2) // 3) * 2 % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3: return bamboo_len - 1\n",
    "        a, b, p = bamboo_len // 3, bamboo_len % 3, 1000000007\n",
    "        if b == 0: return (3 ** a) % p\n",
    "        if b == 1: return ((3 ** (a - 1)) * 4) % p\n",
    "        return ((3 ** a) * 2) % p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        mod = 1000000007\n",
    "        res = 1\n",
    "\n",
    "        if bamboo_len == 2:\n",
    "            return 1\n",
    "        if bamboo_len == 3:\n",
    "            return 2\n",
    "\n",
    "        while bamboo_len > 4:\n",
    "            res = res * 3 % mod\n",
    "            bamboo_len -= 3\n",
    "        return res * bamboo_len % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3:\n",
    "            return bamboo_len-1\n",
    "        p = 1000000007\n",
    "        res = 1\n",
    "        while bamboo_len > 4:\n",
    "            res = res*3%p\n",
    "            bamboo_len -= 3\n",
    "        return res*bamboo_len%p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, n: int) -> int:\n",
    "        if n <= 3: return n - 1\n",
    "        a, b = n // 3, n % 3\n",
    "\n",
    "        if b == 0: return self.remainder(3, a, 1000000007)\n",
    "        elif b == 1: return self.remainder(3, a-1, 1000000007) * 4 % 1000000007\n",
    "        else: return self.remainder(3, a, 1000000007) * 2 % 1000000007\n",
    "\n",
    "    def remainder(self, x, a, p):\n",
    "        rem = 1\n",
    "        while a > 0:\n",
    "            if a % 2: rem = (rem * x) % p\n",
    "            x = x ** 2 % p\n",
    "            a //= 2\n",
    "        return rem\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 2:\n",
    "            return 1\n",
    "        if bamboo_len == 3:\n",
    "            return 2\n",
    "        n = bamboo_len % 3\n",
    "        m = bamboo_len // 3 - 1\n",
    "        mod = 10 ** 9 + 7\n",
    "        if n == 0:\n",
    "            return 3 ** (m + 1) % mod\n",
    "        elif n == 1:\n",
    "            return 4 * (3 ** m) % mod\n",
    "        else:\n",
    "            return 2 * (3 ** (m + 1)) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "def PowerMod (a, b, c):\n",
    "    res, a = 1, a % c\n",
    "    while b > 0:\n",
    "        if b % 2 == 1:\n",
    "            res = (res * a) % c\n",
    "        b = b // 2\n",
    "        a = (a * a) % c\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len==2:return 1\n",
    "        if bamboo_len==3:return 2\n",
    "        MOD = 1000000007\n",
    "        ans=1\n",
    "        split =bamboo_len//3\n",
    "        res = bamboo_len%3\n",
    "        if res==0:\n",
    "            ans=PowerMod(3,split,MOD)\n",
    "        elif res == 1:\n",
    "            ans=PowerMod(3,split-1,MOD)*4%MOD\n",
    "        else:\n",
    "            ans=PowerMod(3,split,MOD)*2%MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3:\n",
    "            return bamboo_len - 1\n",
    "        m = bamboo_len // 3\n",
    "        n = bamboo_len % 3\n",
    "        if n == 0:\n",
    "            len3 = m\n",
    "            len2 = 0\n",
    "        elif n == 1:\n",
    "            len3 = m-1\n",
    "            len2 = 2\n",
    "        else:\n",
    "            len3 = m\n",
    "            len2 = 1\n",
    "        res = 3 ** len3 * 2 ** len2\n",
    "        return res % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        MOD = 1000000007\n",
    "        # q, k, v = 0, 0, 1\n",
    "        # for i in range(3, bamboo_len + 1):\n",
    "        #     v_next = max(1 * v, 2 * k, 3 * q, 1 * (i - 1), 2 * (i - 2), 3 * (i - 3)) % MOD\n",
    "        #     q, k, v = k, v, v_next\n",
    "        # return v\n",
    "        # dp = [0] * (bamboo_len + 1)\n",
    "        # for i in range(2, bamboo_len + 1):\n",
    "        #     for j in range(i):\n",
    "        #         dp[i] = max(dp[i], max(dp[j] * (i - j), j * (i - j)) % MOD)\n",
    "        # return dp[bamboo_len]\n",
    "        if bamboo_len <= 3:\n",
    "            return bamboo_len - 1\n",
    "        a, b = bamboo_len // 3, bamboo_len % 3\n",
    "        rem = 1  # 3^0 % MOD\n",
    "        for i in range(a - 1):\n",
    "            rem = (rem * 3) % MOD\n",
    "        if b == 1:\n",
    "            return ((rem * 2) % MOD * 2) % MOD\n",
    "        elif b == 2:\n",
    "            return ((rem * 3) % MOD * 2) % MOD\n",
    "        else:\n",
    "            return (rem * 3) % MOD\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        if bamboo_len <= 3:  return bamboo_len-1\n",
    "        a, b = bamboo_len//3, bamboo_len%3\n",
    "        if b == 0:\n",
    "            return 3**a %MOD\n",
    "        elif b == 1:\n",
    "            return 3**(a-1)*4 %MOD\n",
    "        else:\n",
    "            return 3**a*2 %MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        mod=1000000007\n",
    "        if bamboo_len<=3:\n",
    "            return bamboo_len-1 \n",
    "        a,b=bamboo_len//3,bamboo_len%3\n",
    "        if b==0:\n",
    "            return 3**a%mod\n",
    "        elif b==1:\n",
    "            return 3**(a-1)*4%mod\n",
    "        else:\n",
    "            return 3**a*2%mod\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        len_1 = bamboo_len\n",
    "        dp = [0] * (len_1 + 1)\n",
    "        dp[2] = 1\n",
    "        res = dp[2]\n",
    "        for i in range(3, len_1 + 1):\n",
    "            for j in range(1, i):\n",
    "                dp[i] = max(dp[i], j * (i - j), j * dp[i-j])\n",
    "                res = max(res, dp[i])\n",
    "        # return res\n",
    "        return int(res % int(1e9 + 7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len) :\n",
    "        if bamboo_len <=3:\n",
    "            return (bamboo_len-1)%1000000007\n",
    "        else:\n",
    "            a = bamboo_len//3\n",
    "            b = bamboo_len%3\n",
    "            if b == 0:\n",
    "                return 3**a%1000000007\n",
    "            elif b==1:\n",
    "                return  3**(a-1)*4%1000000007\n",
    "            elif b==2:\n",
    "                return 3**a*2%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len<=3:\n",
    "            return (bamboo_len-1)*1\n",
    "        else:\n",
    "            three_num = bamboo_len//3\n",
    "            yv = bamboo_len%3\n",
    "            if yv ==0:\n",
    "                return (3**three_num)%1000000007\n",
    "            if yv == 1:\n",
    "                return (3**(three_num-1)*4)%1000000007\n",
    "            elif yv == 2:\n",
    "                return (3**three_num*2)%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3: return bamboo_len - 1\n",
    "        a, b, p, x, rem = bamboo_len // 3 - 1, bamboo_len % 3, 1000000007, 3 , 1\n",
    "        while a > 0:\n",
    "            if a % 2: rem = (rem * x) % p\n",
    "            x = x ** 2 % p\n",
    "            a //= 2\n",
    "        if b == 0: return (rem * 3) % p # = 3^(a+1) % p\n",
    "        if b == 1: return (rem * 4) % p # = 3^a * 4 % p\n",
    "        return (rem * 6) % p # = 3^(a+1) * 2 % p\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3: return bamboo_len - 1\n",
    "        a, b, p, x, rem = bamboo_len // 3 - 1, bamboo_len % 3, 1000000007, 3 , 1\n",
    "        while a > 0:\n",
    "            if a % 2: rem = (rem * x) % p\n",
    "            x = x ** 2 % p\n",
    "            a //= 2\n",
    "        if b == 0: return (rem * 3) % p # = 3^(a+1) % p\n",
    "        if b == 1: return (rem * 4) % p # = 3^a * 4 % p\n",
    "        return (rem * 6) % p # = 3^(a+1) * 2 % p\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\r\n",
    "        if bamboo_len == 2:\r\n",
    "            return 1\r\n",
    "        if bamboo_len == 3:\r\n",
    "            return 2\r\n",
    "        result = [0]*1001\r\n",
    "        result[2] = 2\r\n",
    "        result[3] = 3\r\n",
    "        result[4] = 4\r\n",
    "        for j in range(5,len(result)):\r\n",
    "            result[j] = (result[j-3]*3)%1000000007\r\n",
    "        return result[bamboo_len]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3: return bamboo_len - 1\n",
    "        y = bamboo_len % 3\n",
    "        if y <= 1:\n",
    "            return (3 ** (bamboo_len // 3 - 1) * (3+y)) % 1000000007\n",
    "        else:\n",
    "            return (3 ** (bamboo_len // 3) * y) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        def power_mod(n, p, m):\n",
    "            n_m = 1\n",
    "            for _ in range(p):\n",
    "                n_m = (n_m * n) % m\n",
    "\n",
    "            return n_m\n",
    "\n",
    "        if bamboo_len <= 3:\n",
    "            return bamboo_len - 1\n",
    "        \n",
    "        a = bamboo_len // 3\n",
    "        b = bamboo_len % 3\n",
    "        if b == 1 and a >= 1:\n",
    "            a -= 1\n",
    "            b = 4\n",
    "        return power_mod(3, a, 1000000007) if b == 0 else (power_mod(3, a, 1000000007) * b) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3:\n",
    "            return bamboo_len - 1\n",
    "        a, b, p, x, rem = bamboo_len // 3 - 1, bamboo_len % 3, 1000000007, 3, 1\n",
    "        while a > 0:\n",
    "            if a % 2:\n",
    "                rem = (rem * x) % p\n",
    "            x = x ** 2 % p\n",
    "            a //= 2\n",
    "        if b == 0:\n",
    "            return (rem * 3) % p\n",
    "        if b == 1:\n",
    "            return (rem * 4) % p\n",
    "        return (rem * 6) % p\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3:\n",
    "            return bamboo_len - 1\n",
    "        a, b, res, x, mod = bamboo_len // 3 - 1, bamboo_len % 3, 1, 3, 10 ** 9 + 7\n",
    "        while a:\n",
    "            if a % 2:\n",
    "                res = (res * x) % mod\n",
    "            a //= 2\n",
    "            x = (x * x) % mod\n",
    "        if b == 0:\n",
    "            return res * 3 % mod\n",
    "        elif b == 1:\n",
    "            return res * 4 % mod\n",
    "        else:\n",
    "            return res * 6 % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3: return bamboo_len - 1\n",
    "        a, b, p, x, rem = bamboo_len // 3 - 1, bamboo_len % 3, 1000000007, 3 , 1\n",
    "        while a > 0:\n",
    "            if a % 2: rem = (rem * x) % p\n",
    "            x = x ** 2 % p\n",
    "            a //= 2\n",
    "        if b == 0: return (rem * 3) % p # = 3^(a+1) % p\n",
    "        if b == 1: return (rem * 4) % p # = 3^a * 4 % p\n",
    "        return (rem * 6) % p # = 3^(a+1) * 2 % p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3: return bamboo_len - 1\n",
    "        a, b, p, x, rem = bamboo_len // 3 - 1, bamboo_len % 3, 1000000007, 3 , 1\n",
    "        while a > 0:\n",
    "            if a % 2: rem = (rem * x) % p\n",
    "            x = x ** 2 % p\n",
    "            a //= 2\n",
    "        if b == 0: return (rem * 3) % p # = 3^(a+1) % p\n",
    "        if b == 1: return (rem * 4) % p # = 3^a * 4 % p\n",
    "        return (rem * 6) % p # = 3^(a+1) * 2 % p\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len<=3:\n",
    "            return (bamboo_len-1)*1\n",
    "        else:\n",
    "            three_num = bamboo_len//3\n",
    "            yv = bamboo_len%3\n",
    "            if yv ==0:\n",
    "                return (3**three_num)%1000000007\n",
    "            if yv == 1:\n",
    "                return (3**(three_num-1)*4)%1000000007\n",
    "            elif yv == 2:\n",
    "                return (3**three_num*2)%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len < 3:\n",
    "            return 1\n",
    "        elif bamboo_len == 3:\n",
    "            return 2\n",
    "        res = 1\n",
    "        if bamboo_len % 3:\n",
    "            res = 2\n",
    "            bamboo_len -= 2\n",
    "        MOD = 1000000007\n",
    "        while bamboo_len >= 3:\n",
    "            res = (res * 3) % MOD\n",
    "            bamboo_len -= 3\n",
    "        if bamboo_len:\n",
    "            res = (res * bamboo_len) % MOD\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len<=3:\n",
    "            return bamboo_len-1\n",
    "        a = 1\n",
    "        mod = 1e9+7\n",
    "        while bamboo_len>4:\n",
    "            bamboo_len-=3\n",
    "            a = (a*3)%mod\n",
    "        res = a*bamboo_len%mod\n",
    "        return int(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len == 2:\n",
    "            return 1\n",
    "        if bamboo_len == 3:\n",
    "            return 2\n",
    "\n",
    "        def pow(a, b):\n",
    "            res = 1\n",
    "            p = 1000000007\n",
    "            for i in range(b):\n",
    "                res = (res * a) % p\n",
    "            return res\n",
    "\n",
    "\n",
    "        res = bamboo_len // 3\n",
    "        mod = bamboo_len % 3\n",
    "        p = 1000000007\n",
    "\n",
    "        if mod == 0:\n",
    "            return pow(3, res)\n",
    "        if mod == 1:\n",
    "            return pow(3, res-1)* 4 % p\n",
    "        if mod == 2:\n",
    "            return pow(3,res) * 2 % p\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        n = bamboo_len\n",
    "        dp = [0]*(n+1)\n",
    "        dp[2] = 1\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, i+1):\n",
    "                dp[i] = max(dp[i], j*dp[i-j], j*(i-j))\n",
    "        return dp[-1]%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        if bamboo_len < 4: \n",
    "            return bamboo_len - 1\n",
    "        if bamboo_len % 3 == 0: \n",
    "            return pow(3, bamboo_len // 3, MOD)\n",
    "        if bamboo_len % 3 == 1: \n",
    "            return (pow(3, bamboo_len // 3 - 1, MOD) * 4) % MOD\n",
    "        return (pow(3, bamboo_len // 3, MOD) * 2) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, n: int) -> int:\n",
    "        if n == 2:\n",
    "            return 1\n",
    "        elif n == 3:\n",
    "            return 2\n",
    "        elif n%3 == 0:\n",
    "            return 3**(n//3)%1000000007\n",
    "        elif n%3 == 1:\n",
    "            return 3**(n//3 - 1)*4%1000000007\n",
    "        elif n%3 == 2:\n",
    "            return 3**(n//3)*2%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len<=3:\n",
    "            return (bamboo_len-1)*1\n",
    "        else:\n",
    "            three_num = bamboo_len//3\n",
    "            yv = bamboo_len%3\n",
    "            if yv ==0:\n",
    "                return (3**three_num)%1000000007\n",
    "            if yv == 1:\n",
    "                return (3**(three_num-1)*4)%1000000007\n",
    "            elif yv == 2:\n",
    "                return (3**three_num*2)%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, n: int) -> int:\n",
    "        M = 10 **9 + 7\n",
    "        if n <= 3:\n",
    "            res = n - 1    \n",
    "        elif n % 3 == 0:\n",
    "            res = 3 ** (n // 3)\n",
    "        elif n % 3 == 1:\n",
    "            res = 3 ** (n // 3 - 1) * 4 \n",
    "        else:\n",
    "            res = 3 ** (n // 3) * 2\n",
    "        return res % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3:\n",
    "            return bamboo_len - 1  # 拆分为 1*(bamboo_len-1)\n",
    "\n",
    "        a, b = divmod(bamboo_len, 3)\n",
    "        if b == 0:\n",
    "            return powMod(3, a) % (10**9 + 7)\n",
    "        if b == 1:\n",
    "            # 将 1 * 3 改为 2 * 2\n",
    "            return powMod(3, a - 1) * 4 % (10**9 + 7)\n",
    "        # b == 2\n",
    "        return powMod(3, a) * 2 % (10**9 + 7)\n",
    "\n",
    "\n",
    "def powMod(a, k):\n",
    "    if k == 0:\n",
    "        return 1\n",
    "\n",
    "    if k % 2 == 1:\n",
    "        # 奇数次幂\n",
    "        return (a * powMod(a, k - 1)) % (10**9 + 7)\n",
    "    else:\n",
    "        # 偶数次幂\n",
    "        sub = powMod(a, k // 2)\n",
    "        return (sub * sub) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len<=3:return bamboo_len-1\n",
    "        a,b=bamboo_len//3,bamboo_len%3\n",
    "        ans=1\n",
    "        if not b:\n",
    "            ans=pow(3,a)\n",
    "        elif b==1:\n",
    "            ans=pow(3,a-1)*4\n",
    "        else:\n",
    "            ans=b*pow(3,a)\n",
    "        return ans%(int(1e9)+7)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, n: int) -> int:\n",
    "        if n <= 3:\n",
    "            return n - 1\n",
    "        multiple, remainder = n // 3, n % 3\n",
    "        if remainder == 1:\n",
    "            res = 3 ** (multiple - 1) * 4\n",
    "        elif remainder == 2:\n",
    "            res = 3 ** multiple * 2\n",
    "        else:\n",
    "            res = 3 ** multiple\n",
    "        return res % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        dp=[0]*(bamboo_len+2)\n",
    "        if bamboo_len==1: return 1\n",
    "        if bamboo_len==2: return 1\n",
    "        if bamboo_len==3: return 2\n",
    "        dp[0]=1\n",
    "        dp[1]=1\n",
    "        for i in range(2,bamboo_len+2):\n",
    "            for j in range(1,i):\n",
    "                dp[i]=max(dp[i],dp[j]*(i-j)) \n",
    "        # print(dp)\n",
    "        return dp[-1]%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len<=3:\n",
    "            return (bamboo_len-1)*1\n",
    "        else:\n",
    "            three_num = bamboo_len//3\n",
    "            yv = bamboo_len%3\n",
    "            if yv ==0:\n",
    "                return (3**three_num)%1000000007\n",
    "            if yv == 1:\n",
    "                return (3**(three_num-1)*4)%1000000007\n",
    "            elif yv == 2:\n",
    "                return (3**three_num*2)%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        maxderi=[0]*(bamboo_len+1)\n",
    "        for i in range(2,bamboo_len+1):\n",
    "            for j in range(i):\n",
    "                maxderi[i]=(max(maxderi[i],(i-j)*j,maxderi[i-j]*j,maxderi[j]*(i-j),maxderi[i-j]*maxderi[j]))\n",
    "        return maxderi[bamboo_len]%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        mode = 1e9+7\n",
    "        if bamboo_len == 2:\n",
    "            return 1\n",
    "        elif bamboo_len == 3:\n",
    "            return 2\n",
    "        else:\n",
    "            dp = [0] * bamboo_len\n",
    "            dp[0] = 1\n",
    "            dp[1] = 2\n",
    "            dp[2] = 3\n",
    "            for i in range(3,bamboo_len):\n",
    "                dp[i] = max(3*dp[i-3], 2*dp[i-2])\n",
    "            return int(dp[-1]) % int(1e9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len<=3:\n",
    "            return bamboo_len-1\n",
    "        count3=bamboo_len//3\n",
    "        r=bamboo_len%3\n",
    "        mod=10**9+7\n",
    "        if r==0:\n",
    "            return 3**count3%mod\n",
    "        elif r==1:\n",
    "            return 3**(count3-1)*4%mod\n",
    "        else:\n",
    "            return 3**(count3)*2%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3: return bamboo_len - 1\n",
    "        a, b, p, x, rem = bamboo_len // 3 - 1, bamboo_len % 3, 1000000007, 3 , 1\n",
    "        while a > 0:\n",
    "            if a % 2: rem = (rem * x) % p\n",
    "            x = x ** 2 % p\n",
    "            a //= 2\n",
    "        if b == 0: return (rem * 3) % p # = 3^(a+1) % p\n",
    "        if b == 1: return (rem * 4) % p # = 3^a * 4 % p\n",
    "        return (rem * 6) % p # = 3^(a+1) * 2 % p\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        dp = [0]*(bamboo_len+1) \n",
    "        dp[0], dp[1] = 0, 0\n",
    "        for i in range(2, bamboo_len+1):\n",
    "            for j in range(1, i//2+1):\n",
    "                dp[i] = max(max(j*(i-j), j*dp[i-j]), dp[i])\n",
    "        return dp[-1]%1000000007\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3: return bamboo_len - 1\n",
    "        a, b, p, x, rem = bamboo_len // 3 - 1, bamboo_len % 3, 1000000007, 3 , 1\n",
    "        while a > 0:\n",
    "            if a % 2: rem = (rem * x) % p\n",
    "            x = x ** 2 % p\n",
    "            a //= 2\n",
    "        if b == 0: return (rem * 3) % p # = 3^(a+1) % p\n",
    "        if b == 1: return (rem * 4) % p # = 3^a * 4 % p\n",
    "        return (rem * 6) % p # = 3^(a+1) * 2 % p\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3: return bamboo_len - 1\n",
    "        a, b, p, x, rem = bamboo_len // 3 - 1, bamboo_len % 3, 1000000007, 3, 1\n",
    "        while a > 0:\n",
    "            if a % 2: rem = (rem * x) % p\n",
    "            x = x ** 2 % p\n",
    "            a //= 2\n",
    "        if b == 0: return (rem * 3) % p\n",
    "        if b == 1: return (rem * 4) % p\n",
    "        return (rem * 6) % p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3:\n",
    "            return bamboo_len - 1\n",
    "        quo = bamboo_len // 3\n",
    "        remainder = bamboo_len % 3\n",
    "        def mod_pow(p,mod):\n",
    "            result = 1\n",
    "            for i in range(p):\n",
    "                result = (result*3)%mod\n",
    "            return result\n",
    "        if remainder == 0:\n",
    "            return int(mod_pow(quo,1e9+7))\n",
    "        elif remainder == 1:\n",
    "            return int(mod_pow(quo-1,1e9+7)*4%(1e9+7))\n",
    "        elif remainder == 2:\n",
    "            return int(mod_pow(quo,1e9+7)*2%(1e9+7))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len<=3:\n",
    "            return (bamboo_len-1)*1\n",
    "        else:\n",
    "            three_num = bamboo_len//3\n",
    "            yv = bamboo_len%3\n",
    "            if yv ==0:\n",
    "                return (3**three_num)%1000000007\n",
    "            if yv == 1:\n",
    "                return (3**(three_num-1)*4)%1000000007\n",
    "            elif yv == 2:\n",
    "                return (3**three_num*2)%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, n: int) -> int:\n",
    "        if n <= 3: return n - 1\n",
    "        a, b = n // 3 - 1, n % 3\n",
    "        \n",
    "        # 大数求余（快速幂实现）\n",
    "        p = 1000000007  # 余数\n",
    "        base, rem = 3, 1\n",
    "        while a > 0:\n",
    "            # 奇数情况\n",
    "            if a % 2: \n",
    "                rem = (rem * base) % p\n",
    "            base = base ** 2 % p\n",
    "            a //= 2\n",
    "\n",
    "        if b == 0: return (rem * 3) % p # = 3^(a+1) % p\n",
    "        if b == 1: return (rem * 4) % p # = 3^a * 4 % p\n",
    "        return (rem * 6) % p # = 3^(a+1) * 2 % p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        dp = [0]*(bamboo_len+1)\n",
    "        dp[1] = 1\n",
    "        for i in range(2,bamboo_len+1):\n",
    "            for j in range(i):\n",
    "                dp[i] = max(dp[i],dp[i-j]*j,(i-j)*j)\n",
    "        return dp[-1]%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, n: int) -> int:\n",
    "        # dp = {1:1}\n",
    "        # def dfs(num):\n",
    "        #     if num in dp: return dp[num]\n",
    "        #     dp[num]=0 if num==bamboo_len else num\n",
    "        #     for i in range(1, num):\n",
    "        #         val = dfs(i) * dfs(num-i)\n",
    "        #         dp[num] = max(val, dp[num])\n",
    "        #     return dp[num]\n",
    "        # return dfs(bamboo_len)%1000000007\n",
    "        if n <=3:return n-1\n",
    "        a = 1\n",
    "        mod = 1000000007\n",
    "        while n>4:\n",
    "            n -= 3\n",
    "            a = (a*3)%mod\n",
    "        res = a*n%mod\n",
    "        return int(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len<=3:\n",
    "            return (bamboo_len-1)*1\n",
    "        else:\n",
    "            three_num = bamboo_len//3\n",
    "            yv = bamboo_len%3\n",
    "            if yv ==0:\n",
    "                return (3**three_num)%1000000007\n",
    "            if yv == 1:\n",
    "                return (3**(three_num-1)*4)%1000000007\n",
    "            elif yv == 2:\n",
    "                return (3**three_num*2)%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3: return bamboo_len - 1\n",
    "        a, b, p, x, rem = bamboo_len // 3 - 1, bamboo_len % 3, 1000000007, 3 , 1\n",
    "        while a > 0:\n",
    "            if a % 2: rem = (rem * x) % p\n",
    "            x = x ** 2 % p\n",
    "            a //= 2\n",
    "        if b == 0: return (rem * 3) % p # = 3^(a+1) % p\n",
    "        if b == 1: return (rem * 4) % p # = 3^a * 4 % p\n",
    "        return (rem * 6) % p # = 3^(a+1) * 2 % p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3: return bamboo_len - 1\n",
    "        a, b, p, x, rem = bamboo_len // 3 - 1, bamboo_len % 3, 1000000007, 3 , 1\n",
    "        while a > 0:\n",
    "            if a % 2: rem = (rem * x) % p\n",
    "            x = x ** 2 % p\n",
    "            a //= 2\n",
    "        if b == 0: return (rem * 3) % p # = 3^(a+1) % p\n",
    "        if b == 1: return (rem * 4) % p # = 3^a * 4 % p\n",
    "        return (rem * 6) % p # = 3^(a+1) * 2 % p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        def power(x, a, p):\n",
    "            res = 1 \n",
    "            while a:\n",
    "                if a % 2 == 1:\n",
    "                    res = (res * x) % p \n",
    "                x = x ** 2 % p  \n",
    "                a >>= 1 \n",
    "            return res \n",
    "        if bamboo_len <= 3:\n",
    "            return bamboo_len - 1 \n",
    "\n",
    "        a = bamboo_len // 3\n",
    "        b = bamboo_len % 3\n",
    "        if b == 1:\n",
    "            return power(3, a - 1, 1000000007) * 4 % 1000000007\n",
    "        if b == 2:\n",
    "            return power(3, a, 1000000007) * 2 % 1000000007\n",
    "        return power(3, a, 1000000007)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        dp = [0]*(bamboo_len+1)\n",
    "        dp[1] = 1\n",
    "        for i in range(2,bamboo_len+1):\n",
    "            for j in range(i):\n",
    "                dp[i] = max(dp[i],dp[i-j]*j,(i-j)*j)\n",
    "        return dp[-1]%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        dp = [0] * (bamboo_len + 1)\n",
    "        dp[2] = 1\n",
    "        mod = 1000000007\n",
    "        for i in range(3, bamboo_len + 1):\n",
    "            for j in range(1, bamboo_len):\n",
    "                dp[i] = max(dp[i], max((j * (i - j)), (j * dp[i - j])))\n",
    "        return dp[bamboo_len] % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        # dp指从0 到 bamboo_len\n",
    "        dp = [0] * (bamboo_len + 1)\n",
    "\n",
    "        # 初始化\n",
    "        dp[0] = 0\n",
    "        dp[1] = 0\n",
    "        # dp[2] = 1\n",
    "\n",
    "        for i in range(2,bamboo_len + 1): # 总长度\n",
    "            for j in range(1,i): # 从2起，减去一段\n",
    "                dp[i] = max(dp[i],max(j * (i - j),j * dp[i - j]))\n",
    "        \n",
    "        return dp[bamboo_len]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        n=bamboo_len\n",
    "        if n <= 3: return n - 1\n",
    "        a, b = n // 3, n % 3\n",
    "        if b == 0: return int(math.pow(3, a))\n",
    "        if b == 1: return int(math.pow(3, a - 1) * 4)\n",
    "        return int(math.pow(3, a) * 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3: return bamboo_len - 1\n",
    "        a, b = bamboo_len // 3, bamboo_len % 3\n",
    "        if b == 0: return int(math.pow(3, a))\n",
    "        if b == 1: return int(math.pow(3, a - 1) * 4)\n",
    "        return int(math.pow(3, a) * 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        dp = [0 for _ in range(bamboo_len+1)]\n",
    "        # dp = [0]*(bamboo_len+1)\n",
    "        for i in range(2, bamboo_len+1):  # 从竹子长度为2时，开始迭代\n",
    "            for j in range(1, i-1):\n",
    "                dp[i] = max(dp[i], j*max(i-j, dp[i-j]) )\n",
    "        return dp[bamboo_len]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, n: int) -> int:\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[2] = 1\n",
    "        for i in range(3, n + 1):\n",
    "            for j in range(2, i):\n",
    "                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))\n",
    "        return dp[n]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        dp=[1]*(bamboo_len+1)\n",
    "        ans=1\n",
    "        for i in range(1, bamboo_len+1):\n",
    "            for j in range(1, i):\n",
    "                dp[i]=max(dp[i], dp[j]*(i-j), j*(i-j))\n",
    "\n",
    "        return dp[bamboo_len]%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len == 3:\n",
    "            return 2\n",
    "        dp = [0 for i in range(bamboo_len + 1)]\n",
    "        dp[0] = 1\n",
    "        dp[1] = 1\n",
    "        for i in range(2, bamboo_len + 1):\n",
    "            tmp = 0\n",
    "            for j in range(1, i + 1):\n",
    "                tmp = max(dp[i-j] * j, tmp)\n",
    "            dp[i] = tmp\n",
    "        return dp[bamboo_len]\n",
    "                   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#动态规划\n",
    "#用数组dp[i]记录将正整数i拆分成至少两个正整数的和之后，这些正整数的最大乘积\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3: return bamboo_len - 1\n",
    "        a,b = bamboo_len // 3, bamboo_len % 3 \n",
    "        if b == 0: return int(math.pow(3,a))\n",
    "        if b == 1: return int(math.pow(3,a-1) * 4)\n",
    "        return int(math.pow(3,a) * 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        f = [0] * (bamboo_len + 1)\n",
    "        for i in range(2, bamboo_len + 1):\n",
    "            for j in range(1, i):\n",
    "                f[i] = max(f[i], j * (i - j), j * f[i - j])\n",
    "        return f[bamboo_len]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        if bamboo_len <= 3:  return bamboo_len-1\n",
    "        a, b = bamboo_len//3, bamboo_len%3\n",
    "        if b == 0:\n",
    "            return 3**a %MOD\n",
    "        elif b == 1:\n",
    "            return 3**(a-1)*4 %MOD\n",
    "        else:\n",
    "            return 3**a*2 %MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        # dp[i]的含义是分拆数字i，可以得到的最大乘积为dp[i]\n",
    "        dp = [0 for _ in range(bamboo_len+1)]\n",
    "        dp[2] = 1\n",
    "        for i in range(3,bamboo_len+1):\n",
    "            for j in range(1,i//2+1):\n",
    "                dp[i] = max(dp[i],(i - j) * j,dp[i - j] * j)\n",
    "        return dp[bamboo_len]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len < 4: return bamboo_len - 1\n",
    "        if bamboo_len % 3 == 0: return pow(3, bamboo_len // 3)\n",
    "        if bamboo_len % 3 == 1: return pow(3, bamboo_len // 3 - 1) * 4\n",
    "        return pow(3, bamboo_len // 3) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3:\n",
    "            return bamboo_len - 1\n",
    "        a, b = bamboo_len // 3, bamboo_len % 3\n",
    "        if b == 0:\n",
    "            return int(math.pow(3, a))\n",
    "        elif b == 1:\n",
    "            return int(math.pow(3, a - 1)) * 4\n",
    "        else:\n",
    "            return int(math.pow(3, a)) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, n: int) -> int:\n",
    "        dp = [0] * (n+1)\n",
    "        for i in range(2, n+1):\n",
    "            for j in range(1, i):\n",
    "                dp[i] = max(dp[i], j*(i-j), j*dp[i-j])\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @staticmethod\n",
    "    def ceil4(k):\n",
    "        rest = k-4\n",
    "        if rest <0:\n",
    "            return 0\n",
    "        else:\n",
    "            return (k-4)/3\n",
    "\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len == 3:\n",
    "            return 2\n",
    "        elif bamboo_len == 2:\n",
    "            return 2\n",
    "        if bamboo_len % 3 == 0:\n",
    "            return int(3**(int(bamboo_len/3)))\n",
    "        if bamboo_len % 3 == 1:\n",
    "            return int(3**(Solution.ceil4(bamboo_len))*4)\n",
    "        if bamboo_len % 3 == 2:\n",
    "            return int(3**((bamboo_len-2)/3)*2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        n = bamboo_len\n",
    "        if n <= 3: return n - 1\n",
    "        q, r = divmod(bamboo_len, 3)\n",
    "        if r == 0:\n",
    "            return 3 ** q\n",
    "        elif r == 1:\n",
    "            return 3**(q-1) * 4\n",
    "        else:\n",
    "            return 3 ** q * 2\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3:\n",
    "            return bamboo_len - 1\n",
    "        m = bamboo_len // 3\n",
    "        n = bamboo_len % 3\n",
    "        if n == 0:\n",
    "            len3 = m\n",
    "            len2 = 0\n",
    "        elif n == 1:\n",
    "            len3 = m-1\n",
    "            len2 = 2\n",
    "        else:\n",
    "            len3 = m\n",
    "            len2 = 1\n",
    "        res = 3 ** len3 * 2 ** len2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, n: int) -> int:\n",
    "        if n <= 3: return n - 1\n",
    "        a, b = n // 3, n % 3\n",
    "        if b == 0: return int(math.pow(3, a))\n",
    "        if b == 1: return int(math.pow(3, a - 1) * 4)\n",
    "        return int(math.pow(3, a) * 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3: return bamboo_len - 1\n",
    "        a, b = bamboo_len // 3, bamboo_len % 3\n",
    "        if b == 0: return int(math.pow(3, a))\n",
    "        if b == 1: return int(math.pow(3, a - 1) * 4)\n",
    "        return int(math.pow(3, a) * 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        n = bamboo_len\n",
    "        dp = [0] * (n+1)\n",
    "\n",
    "        for i in range(2, n+1):\n",
    "            for j in range(1, i):\n",
    "                dp[i] = max(dp[i], max(j*dp[i-j], j*(i-j)))\n",
    "        \n",
    "        return dp[n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\r\n",
    "\r\n",
    "class Solution:\r\n",
    "\r\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\r\n",
    "        if bamboo_len == 2:\r\n",
    "            return 1\r\n",
    "        if bamboo_len == 3:\r\n",
    "            return 2\r\n",
    "        result = [0]*(bamboo_len+1)\r\n",
    "        result[2] = 2\r\n",
    "        result[3] = 3\r\n",
    "        result[4] = 4\r\n",
    "        for j in range(5,len(result)):\r\n",
    "            result[j] = result[j-3]*3\r\n",
    "        return result[bamboo_len]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        dp = [0,1,1,2]\n",
    "        for i in range(4, bamboo_len+1):\n",
    "            max_s = 1\n",
    "            for j in range(1, int(i/2)+1):\n",
    "                s = max(j * dp[i-j], j*(i-j))\n",
    "                max_s = max(max_s, s)\n",
    "            dp.append(max_s)\n",
    "        return dp[bamboo_len]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        dp = [0] * (bamboo_len + 1)\n",
    "        for i in range(2, bamboo_len + 1):\n",
    "            for j in range(1, i):\n",
    "                dp[i] = max(dp[i], j * (i - j), j * dp[i - j])\n",
    "        return dp[bamboo_len]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        dp = [0]*(bamboo_len+1)\n",
    "        dp[1] = 1\n",
    "        for i in range(2,bamboo_len+1):\n",
    "            for j in range(i):\n",
    "                dp[i] = max(dp[i],dp[i-j]*j,(i-j)*j)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3:\n",
    "            return bamboo_len - 1\n",
    "        else:\n",
    "            m = bamboo_len % 3\n",
    "            n = bamboo_len // 3\n",
    "            if m == 0:\n",
    "                return 3**n\n",
    "            elif m == 1:\n",
    "                return 3**(n-1) * 4\n",
    "            elif m == 2:\n",
    "                return 3**n * 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3:\n",
    "            return bamboo_len - 1\n",
    "        a, b = bamboo_len // 3, bamboo_len % 3\n",
    "        if b == 0:\n",
    "            return 3**a\n",
    "        if b == 1:\n",
    "            return 3**(a-1) * 4\n",
    "        else:\n",
    "            return 3**a * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\r\n",
    "\r\n",
    "class Solution:\r\n",
    "\r\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\r\n",
    "        if bamboo_len == 2:\r\n",
    "            return 1\r\n",
    "        if bamboo_len == 3:\r\n",
    "            return 2\r\n",
    "        result = [0]*59\r\n",
    "        result[2] = 2\r\n",
    "        result[3] = 3\r\n",
    "        result[4] = 4\r\n",
    "        for j in range(5,len(result)):\r\n",
    "            result[j] = result[j-3]*3\r\n",
    "        return result[bamboo_len]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inner_cut(self, bamboo_len):\n",
    "        if bamboo_len <= 3:\n",
    "            return bamboo_len\n",
    "        else:\n",
    "            return max(3*self.inner_cut(bamboo_len-3), 2*self.inner_cut(bamboo_len-2))\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len == 2:\n",
    "            return 1\n",
    "        elif bamboo_len == 3:\n",
    "            return 2\n",
    "        else:\n",
    "            return self.inner_cut(bamboo_len)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        n = bamboo_len\n",
    "        dp = [0]*(n+1)\n",
    "        for i in range(2, n+1):\n",
    "            for j in range(i):\n",
    "                dp[i] = max(dp[i], j*(i-j), j*dp[i-j])\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len<=3:\n",
    "            return bamboo_len-1\n",
    "        # 对于bamboo_len>=4而言，我们要尽可能的将banboo_len分解为2k+3n\n",
    "        # 显然，2的数量应该<=2，因为任意3个2，可以作为2个3使用，那么8<9\n",
    "        # 那么根据能分成多少个3进行评估\n",
    "        # 若是被3整除，就全分解为3\n",
    "        # 若是余1，代表3k+1，应该分解为k-1个3和2个2\n",
    "        # 若是余2，就代表3k+2，应该分解为k个3和1个2\n",
    "        count3=bamboo_len//3\n",
    "        r=bamboo_len%3\n",
    "        if r==0:\n",
    "            return 3**count3\n",
    "        elif r==1:\n",
    "            return 3**(count3-1)*4\n",
    "        else:\n",
    "            return 3**(count3)*2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        dp = [1] * bamboo_len\n",
    "        for i in range(2, bamboo_len):\n",
    "            for j in range(i):\n",
    "                dp[i] = max(dp[i], (j+1) * (i-j), (j+1) * dp[i-j-1])\n",
    "        # print(dp)\n",
    "        return dp[-1]\n",
    "        \n",
    "        # if bamboo_len <= 3: return bamboo_len-1\n",
    "        # a, b = bamboo_len // 3, bamboo_len % 3\n",
    "        # if b == 0: return int(math.pow(3, a))\n",
    "        # if b == 1: return int(math.pow(3, a-1) * 4)\n",
    "        # return int(math.pow(3, a) * 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        n = bamboo_len\n",
    "        dp = [0]*(n+1)\n",
    "        dp[2] = 1\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, i+1):\n",
    "                dp[i] = max(dp[i], j*dp[i-j], j*(i-j))\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3: return bamboo_len-1\n",
    "        a, b = bamboo_len //3, bamboo_len % 3\n",
    "        if not b: return int(math.pow(3,a))\n",
    "        if b == 1: return int(math.pow(3,a-1) * 4)\n",
    "        \n",
    "        return int(math.pow(3,a) * 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3:\n",
    "            return bamboo_len - 1\n",
    "        quo = bamboo_len // 3\n",
    "        remainder = bamboo_len % 3\n",
    "        if remainder == 0:\n",
    "            return pow(3,quo)\n",
    "        elif remainder == 1:\n",
    "            return pow(3,quo - 1) * 4\n",
    "        elif remainder == 2:\n",
    "            return pow(3,quo) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "\n",
    "        dp = [0]*(bamboo_len+1)\n",
    "        for i in range(2,bamboo_len+1):\n",
    "            for j in range(i):\n",
    "                dp[i] = max(dp[i],j*(i-j),j*dp[i-j])\n",
    "\n",
    "        return dp[bamboo_len]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "#         dp = [0] * bamboo_len\n",
    "#         dp[2] = 1\n",
    "        \n",
    "#         for i in range(3, bamboo_len):\n",
    "#             for j in range(2, i):\n",
    "#                 dp[i] = max(dp[i], dp[j] * (i - j), dp[j] * dp(i - j))\n",
    "            \n",
    "            \n",
    "#         return dp[bamboo_len]\n",
    "        \n",
    "        n = bamboo_len\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[2] = 1\n",
    "        for i in range(3, n + 1):\n",
    "            for j in range(2, i):\n",
    "                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backtrack(self, bamboo_len, remainder):\n",
    "        if remainder == 2:\n",
    "            return 1\n",
    "        if remainder in self.mapping:\n",
    "            return self.mapping[remainder]\n",
    "        res = 1\n",
    "        for i in range(1, remainder):\n",
    "            weight = i\n",
    "            weight *= self.backtrack(bamboo_len, remainder - i)\n",
    "            res = max(res, weight, i * (remainder - i))\n",
    "        self.mapping[remainder] = res\n",
    "        return res\n",
    "        \n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        self.mapping = dict()\n",
    "        return self.backtrack(bamboo_len, bamboo_len)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        dp = [1] * (bamboo_len+1)\n",
    "        dp[2] = 1\n",
    "        if bamboo_len == 1: return 1\n",
    "        if bamboo_len == 2: return 1\n",
    "        if bamboo_len == 3: return 2\n",
    "\n",
    "        for i in range(3, bamboo_len+1):\n",
    "            for j in range(2, i):\n",
    "                dp[i] = max(dp[i], max(j * dp[i-j], j *(i-j)))\n",
    "        print(dp)\n",
    "        return dp[-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len < 2: return 0\n",
    "        if bamboo_len == 2: return 1\n",
    "        if bamboo_len == 3: return 2\n",
    "\n",
    "        dp = [0, 1, 2, 3]\n",
    "        for i in range(4, bamboo_len + 1):\n",
    "            temp = 0\n",
    "            for j in range(1, i):\n",
    "                temp = max(temp, dp[j] * dp[i - j])\n",
    "            dp.append(temp)\n",
    "        return dp[bamboo_len]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        ans, tmp = 1, 0\n",
    "        for i in range(2, bamboo_len):\n",
    "            if bamboo_len % i == 0:\n",
    "                tmp = pow(bamboo_len//i, i)\n",
    "            else:\n",
    "                tmp = pow(bamboo_len//i, i-(bamboo_len%i)) * pow(bamboo_len//i+1, bamboo_len%i)\n",
    "            ans = max(ans, tmp)\n",
    "        return int(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        # dp记录从0到bamboo_len的长度\n",
    "        dp = [0] * (bamboo_len + 1)\n",
    "        dp[0] = 0\n",
    "        dp[1] = 1\n",
    "        dp[2] = 1\n",
    "        for i in range(3,bamboo_len + 1):\n",
    "            for j in range(2,i):\n",
    "                dp[i] = max(dp[i],max(j * (i - j),j * dp[i - j]))\n",
    "\n",
    "\n",
    "        return dp[bamboo_len]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len < 2: return 0\n",
    "        if bamboo_len == 2: return 1\n",
    "        if bamboo_len == 3: return 2\n",
    "\n",
    "        dp = [0, 1, 2, 3]\n",
    "        for i in range(4, bamboo_len + 1):\n",
    "            temp = 0\n",
    "            for j in range(1, i // 2 + 1):\n",
    "                temp = max(temp, dp[j] * dp[i - j])\n",
    "            dp.append(temp)\n",
    "        return dp[bamboo_len]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len < 2: return 0\n",
    "        if bamboo_len == 2: return 1\n",
    "        if bamboo_len == 3: return 2\n",
    "        dp = [0] * (bamboo_len + 1)  # 定义为dp[i]为长度为i时剪绳子后的最大面积\n",
    "        dp[1], dp[2], dp[3] = 1, 2, 3  # 初始值，dp[i]记录的是长度i，这几个极端情况选择不减绳子，值比剪绳子后还大\n",
    "\n",
    "        for i in range(4, bamboo_len + 1):\n",
    "            for j in range(1, i // 2 + 1):\n",
    "                dp[i] = max(dp[i], dp[j] * dp[i - j])  # 转移方程\n",
    "\n",
    "        return dp[bamboo_len]  # 返回值\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3: return bamboo_len - 1\n",
    "        a, b = bamboo_len // 3, bamboo_len % 3\n",
    "        if b == 0: return int(math.pow(3, a))\n",
    "        if b == 1: return int(math.pow(3, a - 1) * 4)\n",
    "        return int(math.pow(3, a) * 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        q, k, v = 0, 1, 1  # len = 0, 1, 2\n",
    "        for i in range(3, bamboo_len + 1):\n",
    "            v_next = max(2 * (i - 2), 3 * (i - 3), 2 * k, 3 * q)\n",
    "            q, k, v = k, v, v_next \n",
    "        return v           \n",
    "        # if bamboo_len in [1, 2]:\n",
    "        #     return 1\n",
    "        # elif bamboo_len == 3:\n",
    "        #     return 2\n",
    "        # else:\n",
    "        #     return max(2 * (bamboo_len - 2), 3 * (bamboo_len - 3), 2 * self.cuttingBamboo(bamboo_len - 2), 3 * self.cuttingBamboo(bamboo_len - 3))            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len < 2: return 0 \n",
    "        \n",
    "        dp = [0] * (bamboo_len + 1)\n",
    "        dp[2] = 1\n",
    "        for i in range(3, bamboo_len + 1):\n",
    "            temp = 0\n",
    "            for j in range(2, i):  # j超过i的一半时，就重复了之前i的过程\n",
    "                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))\n",
    "            dp.append(temp)\n",
    "        return dp[bamboo_len]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        dp = [0] * bamboo_len # dp[i]长度为i+1的竹子的最大乘积\n",
    "        dp[0], dp[1] = 0, 1\n",
    "\n",
    "        for i in range(2, bamboo_len):\n",
    "            for j in range(0, i):\n",
    "                dp[i] = max(dp[i], max((j+1)*dp[i-j-1], (j+1) * (i - j)))\n",
    "        \n",
    "        return dp[bamboo_len - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        dp = [0] * (bamboo_len + 1)\n",
    "        # if ba\n",
    "        # for k in range(len(dp)):\n",
    "        #     dp[k] = k\n",
    "        for i in range(2, bamboo_len + 1):\n",
    "            for j in range(1, i):\n",
    "                dp[i] = max(dp[i],j * (i - j),  j * dp[i - j])\n",
    "        return dp[bamboo_len]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        dp = [0] * (bamboo_len + 1)\n",
    "        dp[1] = 1\n",
    "        for i in range(2, bamboo_len + 1):\n",
    "            max_sum = 0\n",
    "            for j in range(1, i):\n",
    "                max_sum = max(max_sum, (i - j) * j, j * dp[i - j])\n",
    "            dp[i] = max_sum\n",
    "\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        dp = [-1 for i in range(bamboo_len)]\n",
    "        dp[0] = 1\n",
    "        for i in range(1, len(dp)):\n",
    "            for j in range(i):\n",
    "                dp[i] = max(dp[i], max(dp[j], j+1)*max(dp[i-j-1], i-j))\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        q, k, v = 0, 1, 1  # len = 0, 1, 2\n",
    "        for i in range(3, bamboo_len + 1):\n",
    "            v_next = max(2 * (i - 2), 3 * (i - 3), 2 * k, 3 * q)\n",
    "            q, k, v = k, v, v_next \n",
    "        return v           \n",
    "\n",
    "# if bamboo_len in [1, 2]:\n",
    "        #     return 1\n",
    "        # elif bamboo_len == 3:\n",
    "        #     return 2\n",
    "        # else:\n",
    "        #     return max(2 * (bamboo_len - 2), 3 * (bamboo_len - 3), 2 * self.cuttingBamboo(bamboo_len - 2), 3 * self.cuttingBamboo(bamboo_len - 3))            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        # 当 bamboo_len <= 3 时，必须切分出一个 1\n",
    "        if bamboo_len <= 3:\n",
    "            return 1 * (bamboo_len - 1)\n",
    "        # 贪心地切分出 3 ，a 为 3 的个数，b 为余数\n",
    "        a, b = bamboo_len // 3, bamboo_len % 3\n",
    "        if b == 1:\n",
    "            # 当余数为 1 时，将一对 1 * 3 转化为 2 * 2\n",
    "            return int(math.pow(3, a - 1)) * 2 * 2\n",
    "        if b == 2:\n",
    "            # 当余数为 2 时，不做处理\n",
    "            return int(math.pow(3, a)) * 2\n",
    "        # 当余数为 0 时，不做处理\n",
    "        return int(math.pow(3, a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    \r\n",
    "    def getCp(self,queue:Queue):\r\n",
    "        return mul\r\n",
    "        \r\n",
    "\r\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\r\n",
    "        if bamboo_len == 2:\r\n",
    "            return 1\r\n",
    "        if bamboo_len == 3:\r\n",
    "            return 2\r\n",
    "        result = [0]*59\r\n",
    "        result[2] = 2\r\n",
    "        result[3] = 3\r\n",
    "        result[4] = 4\r\n",
    "        for j in range(5,len(result)):\r\n",
    "            result[j] = result[j-3]*3\r\n",
    "        return result[bamboo_len]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len<=3:\n",
    "            return bamboo_len-1\n",
    "        a=bamboo_len//3\n",
    "        b=bamboo_len%3\n",
    "        if b==0:\n",
    "            return 3**a \n",
    "        elif b==1:\n",
    "            return 3**(a-1)*4\n",
    "        elif b==2:\n",
    "            return 3**a*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len < 2: return 0\n",
    "        dp = [0] * (bamboo_len + 1)  # 定义，dp[i]为长度为i时剪绳子后的最大面积\n",
    "        dp[2] = 1 # 初始值\n",
    "\n",
    "        for i in range(3, bamboo_len + 1):\n",
    "            for j in range(1, i):\n",
    "                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))  # 转移方程\n",
    "\n",
    "        return dp[bamboo_len]  # 返回值\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        dp = [1 for _ in range(bamboo_len + 1)]\n",
    "        for i in range(2, bamboo_len + 1):\n",
    "            for j in range(1, i):\n",
    "                dp[i] = max(j * (i - j), j * dp[i - j], dp[i])\n",
    "        return dp[bamboo_len]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3: return bamboo_len - 1\n",
    "\n",
    "        a, b = bamboo_len // 3, bamboo_len % 3\n",
    "\n",
    "        if b == 0: return int(math.pow(3, a))\n",
    "\n",
    "        if b == 1: return int(math.pow(3, a - 1) * 4)\n",
    "\n",
    "        return int(math.pow(3, a) * 2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        # if bamboo_len <= 3: return bamboo_len-1\n",
    "        # a, b = bamboo_len // 3, bamboo_len % 3\n",
    "        # if b == 0: return int(math.pow(3, a))\n",
    "        # if b == 1: return int(math.pow(3, a-1)*4)\n",
    "        # return int(math.pow(3, a)*2)\n",
    "\n",
    "\n",
    "\n",
    "        if bamboo_len < 4: return bamboo_len-1\n",
    "        res = 1\n",
    "        while bamboo_len > 4:\n",
    "            res *= 3\n",
    "            bamboo_len -= 3\n",
    "        return res * bamboo_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        # dp指从0 到 bamboo_len\n",
    "        dp = [0] * (bamboo_len + 1)\n",
    "\n",
    "        # 初始化\n",
    "        dp[0] = 0\n",
    "        dp[1] = 1\n",
    "        dp[2] = 1\n",
    "\n",
    "        for i in range(3,bamboo_len + 1): # 总长度\n",
    "            for j in range(2,i): # 从2起，减去一段\n",
    "                dp[i] = max(dp[i],max(j * (i - j),j * dp[i - j]))\n",
    "        \n",
    "        return dp[bamboo_len]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        q, k, v = 0, 1, 1  # len = 0, 1, 2\n",
    "        for i in range(3, bamboo_len + 1):\n",
    "            v_next = max(2 * (i - 2), 3 * (i - 3), 2 * k, 3 * q)\n",
    "            q, k, v = k, v, v_next \n",
    "        return v           \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <= 3: return bamboo_len - 1\n",
    "        a, b = bamboo_len // 3, bamboo_len % 3\n",
    "        if b == 0: return int(math.pow(3, a))\n",
    "        if b == 1: return int(math.pow(3, a - 1) * 4)\n",
    "        return int(math.pow(3, a) * 2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len<=3:\n",
    "            return bamboo_len-1\n",
    "        a,b=bamboo_len//3,bamboo_len%3\n",
    "        if  b==0:\n",
    "            return int(math.pow(3,a))\n",
    "        if b==1:\n",
    "            return int (math.pow(3,a-1)*4)\n",
    "        if b==2    :\n",
    "            return int(math.pow(3,a)*2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "#         if bamboo_len<=3:\n",
    "#             return bamboo_len-1\n",
    "#         product = 1\n",
    "#         while bamboo_len>4:\n",
    "#             product *= 3\n",
    "#             bamboo_len -= 3\n",
    "#         if bamboo_len != 0:\n",
    "#             return product*bamboo_len\n",
    "#         else:\n",
    "#             return product\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len<=3:\n",
    "            return bamboo_len-1\n",
    "        a = bamboo_len//3\n",
    "        b = bamboo_len%3\n",
    "        if b==1:\n",
    "            return 3**(a-1)*4\n",
    "        if b==2:\n",
    "            return 3**a*b \n",
    "        else:\n",
    "            return 3**a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cuttingBamboo(self, bamboo_len: int) -> int:\n",
    "        if bamboo_len <=3: return bamboo_len - 1\n",
    "        a, b = bamboo_len // 3, bamboo_len % 3\n",
    "        if b == 0: return int(math.pow(3, a))\n",
    "        if b == 1: return int(math.pow(3, a-1)*4)\n",
    "        return int(math.pow(3, a)*2)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
